/**
 * 
 */
package uk.ac.manchester.cs.graph;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * Represents a hypergraph
 * 
 * @author Pavel Klinov
 *
 * pklinov@cs.man.ac.uk, pklinov@clarkparsia.com
 * 
 * Feb 3, 2009
 */
public class HypergraphImpl<V, E> implements Hypergraph<V, E> {

	private Map<V, Set<Hyperedge<V, E>>> m_vertexMap = new HashMap<V, Set<Hyperedge<V, E>>>();
	private Set<Hyperedge<V, E>> m_edges = new HashSet<Hyperedge<V, E>>();
	
	/* 
	 */
	public Hyperedge<V, E> addHyperedge(E object, Set<V> vertices) {

		Hyperedge<V, E> edge = findHyperedge( vertices );
		
		if (null == edge) {
			
			edge = new HyperedgeImpl<V, E>(object, vertices);
			
			for (V vertex : vertices) {
				
				addVertex( vertex );//Won't do anything if the vertex already exists
				m_vertexMap.get( vertex ).add( edge );
			}
			
			m_edges.add( edge );
		}
		
		return edge;
	}

	/* 
	 */
	public void addVertex(V vertex) {
		
		if (!m_vertexMap.containsKey( vertex )) {
			
			m_vertexMap.put( vertex, new HashSet<Hyperedge<V, E>>() );
		}
	}
	
	/* 
	 */
	public Set<V> getAdjacentVertices(V vertex) {

		Set<V> neighbors = new HashSet<V>();
		
		for (Hyperedge<V, E> incident : getIncidentHyperedges( vertex )) {
			
			neighbors.addAll( incident.getVertices() );
		}
		
		neighbors.remove( vertex );
		
		return neighbors;
	}

	/* 
	 */
	public Set<Hyperedge<V, E>> getHyperedges() {

		return m_edges;
	}

	/* 
	 */
	public Set<Hyperedge<V, E>> getIncidentHyperedges(V vertex) {

		return m_vertexMap.get( vertex );
	}

	/* 
	 */
	public int getVertexDegree(V vertex) {

		Set<Hyperedge<V, E>> incidentEdges = getIncidentHyperedges( vertex );
		
		return incidentEdges == null ? 0 : incidentEdges.size();
	}

	/* 
	 */
	public Set<V> getVertices() {

		return m_vertexMap.keySet();
	}

	/* 
	 */
	public void removeHyperedge(Set<V> vertices) {

		Hyperedge<V, E> edge = findHyperedge(vertices);
		
		for (V vertex : vertices) {
			
			getIncidentHyperedges( vertex ).remove( edge );
		}
		
		m_edges.remove( edge );
	}

	
	public Hyperedge<V, E> findHyperedge(Set<V> vertices) {

		V some = null;

		for( V vertex : vertices ) {

			if( m_vertexMap.containsKey( vertex ) ) {

				some = vertex;
				break;
			}
		}

		if( null == some )
			return null;

		for( Hyperedge<V, E> incident : m_vertexMap.get( some ) ) {

			if( (incident.getVertices().size() == vertices.size())
					&& incident.getVertices().containsAll( vertices ) ) {

				return incident;
			}
		}

		return null;
	}
	
	protected void removeHyperedge(Hyperedge<V, E> edge) {
		
		for (V vertex : edge.getVertices()) {
			
			m_vertexMap.get( vertex ).remove( edge );
		}
		
		m_edges.remove( edge );
	}
	/* 
	 */
	public void removeVertex(V vertex) {

		for (Hyperedge<V, E> incident : getIncidentHyperedges( vertex )) {
			
			incident.removeVertex( vertex );
			
			if (incident.getVertices().size() < 2) m_edges.remove( incident );
		}
		
		m_vertexMap.remove( vertex );
	}
	
	/*
	 * Tests the connectivity of the hypergraph
	 */
	public boolean isConnected() {
		//We run simple breadth-first search and check whether all vertices are visited
		Set<V> previous = new HashSet<V>(m_vertexMap.size());
		Set<V> frontier = new HashSet<V>(m_vertexMap.size());
		
		if (!m_vertexMap.isEmpty()) {
			
			frontier.add( m_vertexMap.keySet().iterator().next() );
			bfs(frontier, previous);
			
			return previous.size() == m_vertexMap.size();
			
		} else {
			
			return true;
		}
	}
	
	
	protected void bfs(Set<V> frontier, Set<V> previous) {
		
		while (!frontier.isEmpty()) {
			
			V vertex = frontier.iterator().next();
			Set<V> neighbors = getAdjacentVertices(vertex);
			
			previous.add( vertex );
			frontier.remove( vertex );
			neighbors.removeAll( previous );
			frontier.addAll( neighbors );//TODO To be optimized
		}
	}
}